package Leetcode.Stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        //创建逆波兰表达式
        //(3+4)*5-6   => 3 4 + 5 * 6 -
       /* String suffixExpression= "3 4 + 5 * 6 -";
        *//*1.将3 4 + 5 * 6 -  =》放到List中
        * 2.将list利用方法遍历list配合栈进行计算*//*
        List<String> rpnlist = getList(suffixExpression);
        System.out.println("rpnlist=" +rpnlist);
        int res = calculation(rpnlist);
        System.out.printf("计算结果: %d\n",res);*/


        /*将中缀表达式转换成后缀表达式*/
        //1+((2+3)*4)-5 ====>1 2 3 + 4 * + 5 -
        /*将字符串转换成中缀的list*/
        String expression =  "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("后缀表达式对应的List=" + infixExpressionList);
        List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        //结果List=[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
        System.out.println("后缀表达式对应的List= " + parseSuffixExpressionList);
        //结果 List= [1, 2, 3, +, 4, *, +, 5, -]
        int calculation = calculation(parseSuffixExpressionList);
        System.out.printf("计算结果为：%d\n",calculation);//=16

    }

    /*将字符串转换成中缀的list*/
    public static List<String> toInfixExpressionList(String s){
        List<String> ls= new ArrayList<>();
        int i=0;//指针：遍历中缀字符串
         StringBuilder str;//多位数拼接
        char c;//保存字符 放入c；
        do {
            //c是数字：进行字符串拼接
            if ((c=s.charAt(i))<48 || (c=s.charAt(i))>57){
                ls.add(""+c);
                i++;
            }else {//考虑多位数问题
                str = new StringBuilder();//
                while (i<s.length()&&(c=s.charAt(i))>=48 && (c=s.charAt(i))<=57){
                    str.append(c);
                    i++;
                }
                ls.add(str.toString());
            }
        }while (i<s.length());
        return ls;
    }



    /*中缀表达式转成后缀表达式*/
    public  static  List<String> parseSuffixExpressionList(List<String> ls){
        Stack<String> stackChar = new Stack<>(); //符号栈
        //第二个栈不需要pop操作，而且需要逆向输出所以利用list代替
        List<String> sNum = new ArrayList<>();
        for (String item : ls) {
            /*如果是数入sNum*/
            if (item.matches("\\d+")){
                sNum.add(item);
            }else if (item.equals("(")){
                stackChar.push(item);
            }else if (item.equals(")")){
                /*依次弹出sChar栈顶的运算符，并压入sNum,知道遇到左括号为止，此时将左括号丢弃*/
                while (!stackChar.peek().equals("(")){
                    sNum.add(stackChar.pop());
                }
                stackChar.pop();//将左括号丢弃消除小括号
            }else {
                /*当item的优先级小于等于s1栈顶的运算符的优先级
                * 1.将s1的运算符弹出并加入到s2中，依次比较新的运算符
                * 方法比较运算符的优先级的方法*/
                while (stackChar.size()!=0
                        && Operation.getValue(
                                stackChar.peek())>=
                        Operation.getValue(
                                item)){
                    sNum.add(stackChar.pop());
                }
                //将item压入栈中
                stackChar.push(item);
            }
        }
        /*将s1剩余的运算符压入栈中*/
        while (stackChar.size()!=0){
            sNum.add(stackChar.pop());
        }
        return sNum;//存放到list，因此按顺序输出就是逆波兰表达式
    }

    /*将逆波兰表达式放入到list*/
    public  static List<String> getList(String suffixExpression){
        //字符串分割
        String[] split = suffixExpression.split(" ");
        return new ArrayList<>(Arrays.asList(split));
    }

    /*完成逆波兰运算*/
    public  static  int calculation(List<String> ls){
        //创建一个栈
        Stack<String> stack = new Stack<String>();
        for (String item : ls) {
            /*使用正则表达式*/
            if (item.matches("\\d+")){
                stack.push(item);//入栈
            }else {
                int num2 =Integer.parseInt(stack.pop());//取出pop2个数据进行运算再入栈
                int num1 =Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")){
                    res = num1+num2;
                }else if (item.equals("-")){
                    res = num1-num2;
                }else if (item.equals("*")){
                    res= num1*num2;
                }else if (item.equals("/")){
                    res = num1/num2;
                }else {
                    throw  new RuntimeException("运算符号错误");
                }
                //将结果入栈
                stack.push(res+"");
            }
        }
        //留着栈中的就是计算结果
        return Integer.parseInt(stack.pop());
    }


}
class Operation {
//    PLUS("+", 1),
//    MINUS("-", 1),
//    TIMES("*", 2),
//    DIVIDE("/", 2),
//    LPAREN("(", 0), // 左括号，优先级最低
//    RPAREN(")", 0); // 右括号，优先级最低
//
//    private final String symbol;
//    private final int priority;
//
//    Operation(String symbol, int priority) {
//        this.symbol = symbol;
//        this.priority = priority;
//    }
//
//    public String getSymbol() {
//        return symbol;
//    }
//
//    public int getPriority() {
//        return priority;
//    }

    // getValue方法，接受一个字符串参数，返回操作符的优先级
    public static int getValue(String op) {
        switch (op) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            case "(":
            case ")":
                return 0; // 括号不参与优先级比较
            default:
                throw new IllegalArgumentException("Invalid operation: " + op);
        }
    }
}
